
  //环形链表 II
  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        fast=head;
        //从链表的起点到环的起始点的距离为 x。
        //从环的起始点到快慢指针第一次相遇点的距离为 y。
        //环的总长度为 c。
        //n为循环n次环
        //计算得：x+nc+(c-y)=2*(x+(c-y))
        //即x=(n-1)c+y
        //这里的(n-1)c无论是循环多少次环，都是会回到fast和slow的相遇点的，所以就有x=y
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}